import java.util.HashSet;
import java.util.Set;

/**
 * 874. 模拟行走机器人
 * https://leetcode-cn.com/problems/walking-robot-simulation/
 */
public class Solutions_874 {
    public static void main(String[] args) {
//        int[] commands = {4, -1, 3};
//        int[][] obstacles = {};  // output: 25

//        int[] commands = {4, -1, 4, -2, 4};
//        int[][] obstacles = {{2, 4}};  // output: 65

        int[] commands = {7, -2, -2, 7, 5};
        int[][] obstacles = {{-3, 2}, {-2, 1}, {0, 1},
                {-2, 4}, {-1, 0}, {-2, -3}, {0, -3}, {4, 4}, {-3, 3}, {2, 2}};  // output: 4

        int result = robotSim(commands, obstacles);
        System.out.println(result);
    }

    /**
     * 模拟
     * 1. 将障碍坐标进行哈希值计算后，添加到 set 中
     * 2. 定义转向的操作数组，direct
     * 3. 对每次到达的坐标上，也进行哈希值计算
     *    到达的坐标上是障碍的情况：退回，并继续当前的 command
     *    不是障碍时，继续走后面的 command，走完一步 command 时，最终比较最大的欧式距离
     */
    public static int robotSim(int[] commands, int[][] obstacles) {
        int res = 0;
        // 用 Long 来代替 Integer，因为极端用例 [30000, 30000] 时，int 无法存储
        // set 记录障碍的坐标所计算得到的 long 值
        Set<Long> set = new HashSet<>();
        for (int[] obs : obstacles) {
            // 将障碍坐标，转化为 long 型存储
            set.add(encode(obs[0], obs[1]));
        }
        // 上、右、下、左
        // direct[0] = {1, 0}，表示下一次移动时，y轴坐标 + 1，x轴坐标 + 0
        // direct[3] = {0, -1}，表示下一次移动时，y轴坐标 + 0，x轴坐标 + (-1)
        int[][] direct = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        // 起点坐标为 [0, 0]，默认向上走
        int x = 0, y = 0, dir = 0;

        for (int com : commands) {
            if (com == -2) {
                // 当前移动位置的基础上，左转一次
                dir = (dir + 3) % 4;
            } else if (com == -1) {
                // 当前移动位置的基础上，右转一次
                dir = (dir + 1) % 4;
            } else {
                // 向指定方向走 com 步
                for (int i = 0; i < com; i++) {
                    // 每次走一个单位，到达的坐标
                    x += direct[dir][1];
                    y += direct[dir][0];
                    if (set.contains(encode(x, y))) {
                        // 如果有障碍，停下
                        x -= direct[dir][1];
                        y -= direct[dir][0];
                        break;
                    }
                }
                // 走完再计算
                // 欧式距离计算：到原点的距离，x^2 + y^2
                res = Math.max(res, x * x + y * y);
            }
        }
        return res;
    }

    /**
     * 对坐标 [x, y] 哈希计算成一个 long 型数值，用于将数值记录到 set 中
     * 及判断 [x, y] 在 set 中是否存在
     */
    public static Long encode(int x, int y) {
        // 转化为 long 值
        long newx = (long)x + 30000;
        long newy = (long)y + 30000;
        // 左移 16 位，保证 x 在二进制位的前 16 位，y 在二进制位的后 16 位
        return (newx << 16) + newy;
    }
}
